package com.huawei.M01.iterator.F04;

import java.util.*;

public class NextLargeNode {
    public int[] nextLargerNodes(ListNode head) {
        // 使用单调栈
        List<Integer> res = new ArrayList<>();
        Deque<int[]> deque = new ArrayDeque<>();
        int index = 0;
        while (head != null) {
            index++;
            res.add(0);
            while (!deque.isEmpty() && deque.peek()[0] < head.value) {
                res.set(deque.pop()[1], head.value);
            }
            deque.push(new int[]{head.value, index});
            head = head.next;
        }
        int[] ans = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            ans[i] = res.get(i);
        }
        return ans;
    }

}

class ListNode {
    int value;
    ListNode next;

    public ListNode(int value) {
        this.value = value;
    }

    public ListNode(int value, ListNode next) {
        this.value = value;
        this.next = next;
    }
}